googologywikiaorg-20200223-history
User talk:Vel!/Turing golf
Lychrel numbers The Lychrel number challenge is an uncomputable function! The Turing machine will have to set up to halt if and only if the number is not Lychrel. FB100Z • talk • 18:57, April 14, 2013 (UTC) You are right iff lychrel-ness is undecidable, which I believe it isn't. Even if we can decide this, there is no known algorithm for this, so this is really hard problem. LittlePeng9 (talk) 19:23, April 14, 2013 (UTC) Yes, you are probably correct (I'm not sure, it hasn't been proven). If it is true, then I can invent uncomputable function L(n). Define Lychrel score of the number n to be the largest number of steps (turn and add applications) that need to turn this number into the palindrome. Score can be infinite by your conjecture. Then record score is the largest finite score that doesn't appear in any positive integer number below it. L(n) is the n-th record score. The first few terms can be easily computed: L(1) = 0 (at the number 1) L(2) = 1 (at the number 10) L(3) = 2 (at the number 19) L(4) = 3 (at the number 59) L(5) = 4 (at the number 69) L(6) = 6 (at the number 79) L(7) = 24 (at the number 89) L(8) is unknown, since we don't know whether 196 can be transformed into palindrome or not. Ikosarakt1 (talk ^ 21:19, April 14, 2013 (UTC) Assume being Lychrel is decidable for all numbers. Then there must be an algorithm checking if 196 (or anything else) reaches palindrome without actually simulating whole process (as this might take infinite time). Once again we don't know the algorithm, but it exists (by assumption). Then we could compute L(n) by checking halting times for all non-lychrel numbers (what can be checked by our algorithm). One minor problem may appear if after some point all non-lychrel number form palindrome after bounded time. Then L(n) would be partial (after some point it won't have value, will be undefined) but as long as machine can find values if they exists, function is computable. For undefined arguments, it may run forever. LittlePeng9 (talk) 05:33, April 15, 2013 (UTC) Off topic: FB100Z, your machine has 2c+2 states, not 2c+1. I'm not counting 0 state, as we never use it, but we have read, gl and for every character 2 more. LittlePeng9 (talk) 16:23, April 15, 2013 (UTC) :Thanks for the correction. FB100Z • talk • 22:10, April 15, 2013 (UTC) There are Lychrel numbers in base 2; 22 is the smallest one. This gives me the impression that Lychrel numbers exist in larger bases. FB100Z • talk • 22:21, April 15, 2013 (UTC) Scoring system I believe that our scoring system should be \(s \times c^2\), when don't move option isn't allowed at \((s+1) \times c^2\) otherwise. How about it? Ikosarakt1 (talk ^ ) 13:50, April 20, 2013 (UTC) :Good idea. FB100Z • talk • 19:39, April 20, 2013 (UTC) :I also like it. Number of colors really had to be more significant. LittlePeng9 (talk) 20:04, April 20, 2013 (UTC) Simplest machines FB100Z's addition machine and Ikosarakt's counter are provably simplest machines doing that job. I think there should be note about it. LittlePeng9 (talk) 21:07, May 1, 2013 (UTC) I shall try to find the simplest TMs for other simply problems. Ikosarakt1 (talk ^ ) 09:19, May 2, 2013 (UTC) I managed to find 4-state duplication machine. I started writing how to disprove that there is no such 3-state machine, until I found one :P I'm pretty sure there is no 2-state machine doing this, so I think it is best possible. LittlePeng9 (talk) 09:57, May 2, 2013 (UTC) Your 1-state, 3-color duplication TM actually can multiply two numbers. Entering n 1's and x at end, all separated by m-2 spaces can lead to n*m. For example, 1 1 1 1 x computes 4*3=12, 1 1 1 1 1 1 1 x calculates 7*4=28. Ikosarakt1 (talk ^ ) 15:12, May 3, 2013 (UTC) Time escape Turing machine Is it possible for a TM to simulate with some number of states simulate all TMs with much less number of states? For example, for 100-state TM simulate all 2-state TMs. Ikosarakt1 (talk ^ ) 13:18, June 3, 2013 (UTC) Well, it depends what you exactly mean. First, is such machine supposed to simulate machines with arbitrary number of colours or bounded? In latter case, we can have s*n-state machine simulating n different s-state machine (plus some encoding). Second, do you want that machine to simulate other ones directly or indirectly? In latter case any UTM will do. LittlePeng9 (talk) 14:10, June 3, 2013 (UTC) :I just meant that, say, we have 20736 machines for \(\Sigma(2,2)\), and looking for a possibility to simulate them all for some number of steps. This must be done by the normal TM that can be programmed by our simulator. Ikosarakt1 (talk ^ ) 14:16, June 3, 2013 (UTC) "without" I think adding restrictions of sort "without Hyper-E notation", "without array notation" is pretty much killing the freedom we have when constructing these machines. Also, one can really argue about these things - like in Cloudy's grangol machine he says that his machine can be used to compute Ea#b, which one may argue that it actually sort of computes (part of, but still) E notation. Whatever such challenges which have already been answered should be leaved - I leave it open for discussion, but I think we should remove these new Aarex's challenges and add rule which prohibits such. Also, as a side note (mainly to Aarex): challenges on this page are supposed to be ordered roughly by difficulty, so please, if you can, don't just throw them at the end, but think about where they might fit best. LittlePeng9 (talk) 15:19, April 9, 2014 (UTC) :I agree with that. This is Turing golf; you have to minimize the number of states and symbols, which for most of the challenges can be done by a specialized TM, or a general TM if that is more efficient (such as calculating a^2050b). "Without something" is unnecessary unless the task is complex for some reason. -- ☁ I want more ⛅ 15:48, April 9, 2014 (UTC) :it's like saying "prove that the length of the diagonal of a cube is \(\sqrt{3}\), without using the pythagorean theorem." no matter what you do, there will be an implicit invocation of the forbidden middleman you're.so. 23:57, April 9, 2014 (UTC) ::Sure, I'll try. Consider a regular hexagon. Draw the three main diagonals (splitting it into 6 triangles) and three smaller diagonals making a big triangle. You get 12 identical pieces. As is easily seen, the small triangles consist of 2 pieces each, while the big one consists of 6. This means that the big triangle has 3 times as much area, so its sides are \(\sqrt{3}\) times as long as the smaller triangle's sides; thus the altitude of an equilateral triangle, being half of the large triangle's side, is \(\sqrt{3}/2\) times as long as the side. Using the formula for the area, we find that an equilateral triangle's area is \(\sqrt{3}/4\) times the square of the side. Now we return to the cube. Consider a corner part of the cube cut off by a plane passing through three vertices next to the corner. By symmetry, it is perpendicular to the diagonal going from that corner, and its cross-section from the cube is an equilateral triangle. As such, it can be considered a pyramid, with its base being the relevant section of the diagonal. Note that, by considering it as a pyramid in a different way (the height being one of the edge from our corner, and the base half of the side formed by the other two edges), we can calculate that its volume is 1/6. By considering a similar plane in the opposite corner, we easily see by Thales' theorem that the height of our diagonal pyramid is 1/3 of the length of the diagonal. Meanwhile, its base is an equilateral triangle whose sides are side diagonals; a construction similar to the hexagon one above (I won't detail it here) shows that the square of such a diagonal is 2, so the area of the triangle is \(\sqrt{3}/4\) times 2, or \(\sqrt{3}/2\). Now let the full diagonal length be x; then the pyramid with height x/3 and base area \(\sqrt{3}/2\) has volume 1/6, that is to say, \((x/3)(\sqrt{3}/2)/3=1/6\); this gives \(x\sqrt{3}/3=1\), or \(x=3/\sqrt{3}=\sqrt{3}\), Q.E.D. Now show me where I used the Pythagorean theorem :-) Just kidding; I do kind of see your point (and your example will still work if we consider, say, a figure made of two cubes put together, whose diagonal is \(\sqrt{6}\)). --Январь Первомайский (talk) 19:13, July 1, 2015 (UTC) ::::Nice proof, but could you clarify how you got that the height of pyramid in a corner is 1/3 of whole diagonal? ::::Also, if one wanted, one could replace every instance of Pythagorean theorem by the following (simple enough) proof: in a right triangle drop an altitude from the right angle and consider similar triangles which appear that way (for details see here). This one might be actually considered cheating, but hey, it doesn't use Pythagorean theorem per se :) LittlePeng9 (talk) 19:37, July 1, 2015 (UTC) :::::Consider the base of our corner pyramid together with the equivalent plane in the opposite corner; they divide our diagonal into three parts. Consider a triangle formed by one of the side diagonals coming out of our corner and the relevant two parts of the diagonal; then its intersection with the opposite corner plane is its base, and its intersection with the pyramid base plane is parallel to it (because the two planes are parallel) and starts in the midpoint of the side diagonal. Then, by Thales' theorem, it intersects the other side in the middle, i.e. the pyramid height is equal to the middle part; by symmetry, all three parts are equal, which makes each of them 1/3 of the full diagonal. Q.E.D. And yes, I suppose one could just switch the theorem for a simple proof of it (not necessarily the one you gave - there are many other simple ones), but that isn't really so much "not using the theorem" as just proving it directly before using the result anyway. It's apparently Thales, not Phales, incidentally (I fixed that, and a few other small things, in my original post). --Январь Первомайский (talk) 20:48, July 1, 2015 (UTC) ::::::I retract my double-cube claim - it turns out to be an easy corollary of the cube proof (actually, it doesn't even need the full cube proof, just the triangle and square calculations). That said, I believe that the statement could well still be correct if we consider the triple cube (diagonal \(\sqrt{11}\)) or the 1-2-4 brick (diagonal \(\sqrt{21}\)). --Январь Первомайский (talk) 23:59, July 2, 2015 (UTC) FOST golf Why not make a FOST version of this? Fluoroantimonic Acid (talk) 16:09, July 1, 2015 (UTC) :I just guess that no one ever bothered to create FOST golf. It's not that bad of an idea. LittlePeng9 (talk) 16:51, July 1, 2015 (UTC) :It seems me easier to make than turing machines Fluoroantimonic Acid (talk) 17:35, July 1, 2015 (UTC) ::As soon as you grasp how to define arithmetic structures and alike, that's probably true, but that of course depends on the person you ask. LittlePeng9 (talk) 17:51, July 1, 2015 (UTC)